{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Digit sum of all digits in a number\n",
    "def digit_sum(input_number):\n",
    "    if input_number == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return input_number%10 + digit_sum(input_number//10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digit_sum(2453)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Calculating the factorial of a number\n",
    "def fact(input_number):\n",
    "    if input_number == 0 or input_number == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return input_number * fact(input_number-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fact(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Factorial with memoization\n",
    "memo = dict()\n",
    "def fact(input_number):\n",
    "    if input_number == 0 or input_number == 1:\n",
    "        return 1\n",
    "    elif input_number in memo:\n",
    "        return memo[input_number]\n",
    "    else:\n",
    "        memo[input_number] = input_number*fact(input_number-1)\n",
    "        return memo[input_number]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fact(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Permute all letters of a string\n",
    "def permute(input_string):\n",
    "    if len(input_string) == 1:\n",
    "        return [input_string]\n",
    "    else:\n",
    "        out = set()\n",
    "        for i,char in enumerate(input_string):\n",
    "            for perm in permute(input_string[:i]+input_string[i+1:]):\n",
    "                out.add(char+perm)\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Vhiis',\n",
       " 'Vhisi',\n",
       " 'Vhsii',\n",
       " 'Vihis',\n",
       " 'Vihsi',\n",
       " 'Viihs',\n",
       " 'Viish',\n",
       " 'Vishi',\n",
       " 'Visih',\n",
       " 'Vshii',\n",
       " 'Vsihi',\n",
       " 'Vsiih',\n",
       " 'hViis',\n",
       " 'hVisi',\n",
       " 'hVsii',\n",
       " 'hiVis',\n",
       " 'hiVsi',\n",
       " 'hiiVs',\n",
       " 'hiisV',\n",
       " 'hisVi',\n",
       " 'hisiV',\n",
       " 'hsVii',\n",
       " 'hsiVi',\n",
       " 'hsiiV',\n",
       " 'iVhis',\n",
       " 'iVhsi',\n",
       " 'iVihs',\n",
       " 'iVish',\n",
       " 'iVshi',\n",
       " 'iVsih',\n",
       " 'ihVis',\n",
       " 'ihVsi',\n",
       " 'ihiVs',\n",
       " 'ihisV',\n",
       " 'ihsVi',\n",
       " 'ihsiV',\n",
       " 'iiVhs',\n",
       " 'iiVsh',\n",
       " 'iihVs',\n",
       " 'iihsV',\n",
       " 'iisVh',\n",
       " 'iishV',\n",
       " 'isVhi',\n",
       " 'isVih',\n",
       " 'ishVi',\n",
       " 'ishiV',\n",
       " 'isiVh',\n",
       " 'isihV',\n",
       " 'sVhii',\n",
       " 'sVihi',\n",
       " 'sViih',\n",
       " 'shVii',\n",
       " 'shiVi',\n",
       " 'shiiV',\n",
       " 'siVhi',\n",
       " 'siVih',\n",
       " 'sihVi',\n",
       " 'sihiV',\n",
       " 'siiVh',\n",
       " 'siihV'}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "permute(\"Vishi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "60"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(set(permute(\"Vishi\")))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Permute all words in a list of list to create sentences\n",
    "def permute(input_list):\n",
    "    if len(input_list) == 1:\n",
    "        return input_list[0]\n",
    "    else:\n",
    "        out = set()\n",
    "        for i,elem in enumerate(input_list[0]):\n",
    "            for perm in permute(input_list[1:]):\n",
    "                out.add(elem+perm)\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Iamgreat', 'Iaregreat', 'Weamgreat', 'Wearegreat'}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "permute([['I','We'],['am','are'],['great']])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Coin change problem\n",
    "def coin_change(target, coins):\n",
    "    if target == 0:\n",
    "        return 1\n",
    "    if target < 0:\n",
    "        return 0\n",
    "    if len(coins) == 0:\n",
    "        return 0\n",
    "    return coin_change(target, coins[1:]) + coin_change(target-coins[0], coins) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change(8,[1,2,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def coin_change(target,coins):\n",
    "    if target == 0:\n",
    "        return True\n",
    "    if target < 0:\n",
    "        return False\n",
    "    if len(coins) == 0:\n",
    "        return False\n",
    "    return coin_change(target, coins[1:]) or coin_change(target-coins[0], coins)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coin_change(8,[1,2,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Array with index as numbers has complete list\n",
    "def is_complete_cycle(input_list):\n",
    "    for index in range(0,len(input_list)):\n",
    "        count = len(input_list)\n",
    "        curr_index = index\n",
    "        print(index)\n",
    "        while(count >0):\n",
    "            \n",
    "            curr_index = (curr_index + input_list[curr_index])%len(input_list)\n",
    "            count -= 1\n",
    "            print(curr_index)\n",
    "        if curr_index == index:\n",
    "            return True\n",
    "    return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Tripple step \n",
    "def tripple_step(target, steps):\n",
    "    if target == 0:\n",
    "        return 1\n",
    "    if target < 0:\n",
    "        return 0\n",
    "    res = 0\n",
    "    for step in steps:\n",
    "        res += tripple_step(target-step,steps)\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tripple_step(5,[1,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Subsets in a set\n",
    "def subsets(input_set):\n",
    "    if len(input_set) == 0:\n",
    "        return [[]]\n",
    "    result = []\n",
    "    previous = subsets(input_set[1:])\n",
    "    for subset in previous:\n",
    "        result.append(subset+[input_set[0]])\n",
    "    result.append(previous)\n",
    "    return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['a'], [[]]]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "subsets(['a'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Robot in a grid\n",
    "class Point:\n",
    "    def __init__(self,x,y):\n",
    "        self.x_corr = x\n",
    "        self.y_corr = y\n",
    "    def __eq__(self, p):\n",
    "        return self.x_corr == p.x_corr and self.y_corr == p.y_corr\n",
    "def find_path(curr_x, curr_y, path, invalid_points, r, c):\n",
    "    print(curr_x,curr_y)\n",
    "    if curr_x <0 or curr_x>=r or curr_y<0 or curr_y>=c:\n",
    "        return False\n",
    "    current_point = Point(curr_x, curr_y)\n",
    "    if current_point == Point(r-1,c-1):\n",
    "        return True\n",
    "    if (find_path(curr_x+1, curr_y, path, invalid_points, r, c) or find_path(curr_x, curr_y+1, path, invalid_points, r, c)) and current_point not in invalid_points:\n",
    "        path.append(current_point)\n",
    "        return True\n",
    "    else:\n",
    "        invalid_points.append(current_point)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0\n",
      "1 0\n",
      "2 0\n",
      "1 1\n",
      "[<__main__.Point object at 0x000001FECB113F98>, <__main__.Point object at 0x000001FECB113E80>]\n"
     ]
    }
   ],
   "source": [
    "current_point = Point(0,0)\n",
    "path = []\n",
    "invalid_points = []\n",
    "r = 2\n",
    "c = 2\n",
    "if find_path(0,0,path,invalid_points,r,c):\n",
    "    print(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Finding a magic index in a list\n",
    "def magic_index(input_list):\n",
    "    size = len(input_list)\n",
    "    if size is not 0:\n",
    "        index = size//2\n",
    "        if input_list[index] ==index:\n",
    "            return index\n",
    "        elif input_list[index] > index:\n",
    "            return magic_index(input_list[:index])\n",
    "        else:\n",
    "            return magic_index(input_list[index+1:])\n",
    "    return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "magic_index([-5,-1,2,6,7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def magic_index(input_list):\n",
    "    size = len(input_list)\n",
    "    if size is not 0:\n",
    "        index = size//2\n",
    "        if input_list[index] == index:\n",
    "            return index\n",
    "        elif input_list[index] > index:\n",
    "            return magic_index(input_list[:input_list[index]])\n",
    "        else:\n",
    "            return magic_index(input_list[input_list[index]:])\n",
    "    return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "magic_index([1,2,2,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Permutation of a string\n",
    "def permute(input_string):\n",
    "    if len(input_string) == 1:\n",
    "        return set([input_string])\n",
    "    out = set()\n",
    "    for i,char in enumerate(input_string):\n",
    "        for perm in permute(input_string[:i]+input_string[i+1:]):\n",
    "            out.add(perm+char)\n",
    "    return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'aaaaa'}"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "permute('aaaaa')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Permutation of a list of list\n",
    "def permute(input_list):\n",
    "    if len(input_list) == 1:\n",
    "        return input_list[0]\n",
    "    out = list()\n",
    "    for i,char in enumerate(input_list[0]):\n",
    "        for perm in permute(input_list[1:]):\n",
    "            out.append(char+perm)\n",
    "    return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Iamgreat', 'Iaregreat', 'Weamgreat', 'Wearegreat']"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "permute([['I','We'],['am','are'],['great']])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a set of correct parenthesis\n",
    "def parens(count):\n",
    "    if count == 1:\n",
    "        return set(['()'])\n",
    "    out = set()\n",
    "    for perm in parens(count-1):\n",
    "        for i in range(len(perm)):\n",
    "            out.add(perm[:i]+'()'+perm[i:])\n",
    "    return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'((()))', '(()())', '(())()', '()(())', '()()()'}"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parens(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
